import { swap } from './utils'

// 获取节点的父元素
function parent (index) {
  return Math.floor(Math.abs((index - 1) / 2))
}

// index位置的元素入堆
function heapInsert (arr, index) {
  while (arr[index] > arr[parent(index)]) {
    swap(arr, index, parent(index))
    index = parent(index)
  }
}

function heapify (arr, index, heapSize) {
  let left = 2 * index + 1
  while (left < heapSize) {
    const largerIndex = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left
    if (arr[largerIndex] > arr[index]) {
      swap(arr, largerIndex, index)
      index = largerIndex
      left = 2 * index + 1
    } else {
      break
    }
  }
}

function heapSort (arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  for (let i = 0; i < arr.length; i++) {
    heapInsert(arr, i)
  }
  let heapSize = arr.length
  swap(arr, 0, --heapSize) // 堆顶出堆
  while (heapSize > 0) {
    heapify(arr, 0, heapSize)
    swap(arr, 0, --heapSize)
  }
}

const arr2 = [9, 5, 8, 7, 5, 6, 5, 4, 5, 3, 2, 1]
heapSort(arr2)
console.log(arr2)
